package algorithm7.leetcode.每日一题.YEAR2023.month7;

import org.junit.jupiter.api.Test;

import java.util.Stack;

/**
 * @Author: permission
 * @Date: 2023/7/4 0:26
 * @Version: 1.0
 * @ClassName: DAY20230703_LC445
 * @Description:
 */
public class DAY20230703_LC445 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return handle1(l1, l2);
    }

    // 逆序用栈
    private ListNode handle1(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode ans = null;
        // 进位信息
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int c = a + b + carry;
            // 进位
            carry = c / 10;
            c = c % 10;
            ListNode curNode = new ListNode(c);
            curNode.next = ans;
            ans = curNode;
        }
        return ans;
    }

/*
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：
输入：l1 = [0], l2 = [0]
输出：[0]

 */

    @Test
    void test() {
        ListNode l1 = new ListNode(2);
        ListNode l12 = new ListNode(4);
        l1.next = l12;
        l12.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        ListNode l22 = new ListNode(6);
        l2.next = l22;
        l22.next = new ListNode(4);

        ListNode res = addTwoNumbers(l1, l2);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}


